{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. 画图解释图像卷积滤波的基本原理，并进一步简述常见的图像平滑滤波算法。 \n",
    "\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;图像滤波的基本原理是一个二维的滤波矩阵(假设是3x3),作用于图像中的每个像素点和这个像素点相邻的像素点(也是3x3),作用方式是每个对应位置的值相乘然后相加作为该像素位置的值。如下图：\n",
    "![卷积滤波原理](http://px71ub40t.bkt.clouddn.com/1.png)\n",
    "常见的平滑滤波算法有：  \n",
    "**平均滤波：** 取一个小区域内像素值的平均。平均滤波的算子为：\n",
    "![边缘类型](http://px71ub40t.bkt.clouddn.com/TIM%E6%88%AA%E5%9B%BE20190911192959.png)\n",
    "\n",
    "**加权平均滤波：** 也叫高斯滤波，是在平均滤波基础上加上一个权值，使得中心区域的像素作用更大。 高斯滤波的算子为：\n",
    "![边缘类型](http://px71ub40t.bkt.clouddn.com/TIM%E6%88%AA%E5%9B%BE20190911193119.png)\n",
    "\n",
    "**中值滤波：** 在一个区域内（含奇数个像素）按照灰度大小排序，然后取中间的值代替这个区域的中心像素值。中值滤波原理为：\n",
    "![边缘类型](http://px71ub40t.bkt.clouddn.com/TIM%E6%88%AA%E5%9B%BE20190911193257.png)\n",
    "\n",
    "**形态学滤波：** 形态学滤波通常用多步操作组成。膨胀是求图像像素局部最大值的操作，对图像中高亮部分进行膨胀。腐蚀与膨胀相反，是求图像局部最小值的算法。开运算是先腐蚀再膨胀，闭运算是先膨胀再腐蚀。  \n",
    "膨胀的原理图：\n",
    "![边缘类型](http://px71ub40t.bkt.clouddn.com/TIM%E6%88%AA%E5%9B%BE20190911194049.png)\n",
    "腐蚀的原理图：\n",
    "![边缘类型](http://px71ub40t.bkt.clouddn.com/TIM%E6%88%AA%E5%9B%BE20190911194124.png)\n",
    "\n",
    "### 2. 简述边缘检测的基本原理，以及Sobel、LoG和Canny算子的原理差异。 \n",
    "\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;边缘是图像上灰度变化最明显的地方，传统的边缘检测利用此特点对图像的各像素点进行求微分和二阶微分来定位边缘点。由灰度变化的特点，可以将边缘类型分为阶梯状、脉冲状和屋顶状三种。对于阶梯状，图像边缘点对应一阶微分图像的峰值和二阶微分图像的零交叉处；对于脉冲状和屋顶状边缘，边缘对应一阶导数的零交叉和二阶导数的峰值。如下图所示：\n",
    "\n",
    "![边缘类型](http://px71ub40t.bkt.clouddn.com/TIM%E6%88%AA%E5%9B%BE20190910213635.png)\n",
    "\n",
    "**Sobel算子：**  Sobel算子主要用于获取数字图像的一阶梯度，它是使用一个卷积核对原始图像进行卷积，分别得到横向G(x)和纵向G(y)的梯度值，如果梯度值大于某一个阈值，则认为该点是边缘点。Sobel算子的卷积核为：\n",
    "![Sobel算子的卷积核](http://px71ub40t.bkt.clouddn.com/TIM%E6%88%AA%E5%9B%BE20190911215302.png)\n",
    "根据上图的卷积核对图像进行卷积的公式为：\n",
    "![Sobel卷积算法](http://px71ub40t.bkt.clouddn.com/GxGy.png)  \n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Sobel算子根据像素点上下、左右邻点灰度加权差，在边缘处达到极值来检测边缘。当对精度要求不是很高时，是一种较为常用的边缘检测方法。   \n",
    "      \n",
    "**LoG算子：**  通过一阶导数确定边缘时（Sobel算子等）会存在以下问题：1、在噪声处一阶导数也会取极大值。2、求解极大值的复杂性。所以，我们有了使用二阶导数的算法，一阶导数的极大值在求二阶导数时为0。LoG算子时先对图像进行高斯模糊，然后再求解二阶导数，二阶导数等于0处对应的像素就是图像的边缘。步骤如下：  \n",
    "1.对图像先进性高斯滤波（G × f），再进行Laplace算子运算Δ（G × f）；  \n",
    "2.保留一阶导数峰值的位置，从中寻找Laplace过零点；  \n",
    "3.对过零点的精确位置进行插值估计。  \n",
    "原始图像f(x,y) 与高斯卷积定义为：\n",
    "![LoG定义](http://px71ub40t.bkt.clouddn.com/LoG.png)   \n",
    "常用的模板为：  \n",
    "![LoG卷积模板](http://px71ub40t.bkt.clouddn.com/LoG%E6%A8%A1%E6%9D%BF.png)  \n",
    "**Canny算子：**  图像边缘信息主要集中在高频段，通常说图像锐化或检测边缘，实质就是高频滤波。我们知道微分运算是求信号的变化率，具有加强高频分量的作用。在空域运算中来说，对图像的锐化就是计算微分。由于数字图像的离散信号，微分运算就变成计算差分和梯度。图像处理中有多种边缘检测算子，常用的包括一阶差分（Sobel算子），二价差分（LoG算子）。Canny算子求边缘点具体算法步骤如下：  \n",
    "1.用高斯滤波器平滑图像。  \n",
    "2.用一阶偏导有限差分计算梯度幅值和方向。  \n",
    "3.对梯度幅值进行非极大值抑制。  \n",
    "4.用双阈值算法检测和连接边缘。  \n",
    "\n",
    "**三种算子的特点：**    \n",
    "Sobel算子产生的边缘有强弱，抗噪行好，计算量小；  \n",
    "LoG算子对边缘敏感，可能有些是噪声的边缘也被算进来了；  \n",
    "Canny产生的边缘很细，可能就一个像素那么细，没有强弱之分。计算量大但是准确。  \n",
    "\n",
    "### 3. 简述图像直方图的基本概念，及使用大津算法进行图像分割的基本原理。   \n",
    "\n",
    "**图像直方图：**  是将图像中各个像素点的灰度级别及该级别出现的次数或频率绘制的直方图。下图是lena灰度图像的直方图：\n",
    "![直方图](http://px71ub40t.bkt.clouddn.com/%E7%9B%B4%E6%96%B9%E5%9B%BE.png)   \n",
    "\n",
    "**大津算法的基本原理：** 最大类间方差是由日本学者大津与1979年提出，是一种自适应的阈值确定方法。算法假设图像像素能够根据阈值，被分成背景和目标两部分，然后计算最佳阈值来区分这两类像素，使得两类像素区分度最大。下图是计算过程：   \n",
    "![大津算法](http://px71ub40t.bkt.clouddn.com/%E5%85%AC%E5%BC%8F.png) \n",
    "\n",
    "\n",
    "### 4. 简述Harris算子对角点的定义，进行角点检测的基本原理，并说明引入角点响应函数的意义。  \n",
    "\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Harris算子是Harris和Stephens在1998年提出的一种基于信号的点特征提取算子。其前身是Moravec算子。其基本思想是：在图像中设计一个局部检测窗口，当该窗口沿各个方向做微小移动时，考察窗口的灰度积分变化，当积分变化超过设定的阈值时，就将窗口的中心像素点提取为角点。  \n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Harris算子定义灰度积分变化公式：  \n",
    "![Harris积分公式](http://px71ub40t.bkt.clouddn.com/Harris1.png)   \n",
    "上图中w(x,y)表示窗口矩阵，M矩阵为偏导数矩阵。对于矩阵可以进行对称矩阵的变化，假设利用两个特征值进行替代，其几何含义类似于下图中的表达：  \n",
    "![Harris积分公式](http://px71ub40t.bkt.clouddn.com/Harris2.png)    \n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;M为梯度的协方差矩阵，在实际应用中为了能够应用更好的编程，定义了角点响应函数R，通过判断R大小来判断像素是否为角点。R取决于M的特征值，对于角点|R|很大，平坦区域|R|很小，边缘的R为负值。角点响应函数定义如下：\n",
    "![Harris积分公式](http://px71ub40t.bkt.clouddn.com/Harris3.png)   \n",
    "\n",
    "\n",
    "### 5. 简述Hough变换的基本原理(包括参数空间变换及参数空间划分网格统计)。  \n",
    "\n",
    "**Hough变换的基本原理：** 使用Hough变换来检测直线的思想就是为每一个点假设n个方向的直线,通常n=180,此时检测的直线角度精度为1,分别计算这n条直线的(ρ,θ)坐标，得到n个坐标点。如果要判断的点共有m个，最终的到(ρ,θ)坐标共有m * n个，其中θ是离散的角度，共有180个取值。如果多个点在一条直线上，那么必有这多个点在θ等于某个值时，ρ近似相等。在x-y图像空间中的一个点转换到极坐标空间表示如下图:\n",
    "![坐标空间转换](http://px71ub40t.bkt.clouddn.com/%E7%A9%BA%E9%97%B4%E8%BD%AC%E6%8D%A2.png)   \n",
    "公式表示为:![坐标空间转换](http://px71ub40t.bkt.clouddn.com/%E5%85%AC%E5%BC%8F1.png)   \n",
    "Hough变换检测直线步骤：  \n",
    "1、将(ρ,θ)空间量化成许多小格；  \n",
    "2、根据x-y平面每一个直线点代入θ的量化值，算出各个ρ,将对应格计数累加；  \n",
    "3、当全部点变换后，对小格进行校验。设置累计阈值T，计数器大于T的小格对应于共线点，其可以用作直线拟合参数。小于T的是非共线点，丢弃不用；\n",
    "\n",
    "\n",
    "### 6. 简述SIFT原理(重点是尺度空间和方向直方图原理)及ORB算子原理(重点是FAST和BRIEF)。\n",
    "\n",
    "**SIFT原理：** SIFT算法的实质是在不同的尺度空间上查找关键点(特征点)，并计算出关键点的方向。SIFT算法的特点有：  \n",
    "1、图像的局部特征，对旋转、尺度缩放、亮度变化保持不变，对视角变化、仿射变换噪声也保持一定的稳定性。  \n",
    "2、独特性好，信息量丰富，适用于海量特征库进行快速、准确的匹配。  \n",
    "3、多量性：即使是很少几个物体也可以产生大量的SIFT特征。  \n",
    "4、高速性：改进的SIFT匹配算法甚至可以达到实时性。  \n",
    "5、扩展性：可以很方便的与其他的特征向量进行联合。    \n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;尺度空间的获取需要使用高斯模糊来实现。通过高斯函数与与原图像卷积，并经过下采样，可建立原始图像的尺度空间模型。二维高斯函数模板上的元素(x,y)对应的高斯计算公式为：  \n",
    "![二维高斯函数](http://px71ub40t.bkt.clouddn.com/%E9%AB%98%E6%96%AF%E5%87%BD%E6%95%B0.png)  \n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;尺度空间理论：在图像信息处理模型中引入一个被视为尺度的参数，通过连续变化的尺度参数获得多尺度下尺度空间表示序列，对这些序列进行尺度空间主轮廓的提取，并以该主轮廓作为一种特征向量，实现边缘、角点检测和不同分辨率上的特征提取等。尺度空间方法将传统的单尺度图像信息处理技术纳入尺度不断变化的动态分析框架中，更容易获取图像的本质特征。尺度空间中各尺度图像的模糊程度逐渐变大，能够模拟人在距离目标由近到远时目标在视网膜上的形成过程。  \n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;尺度空间在使用时使用高斯金字塔表示，高斯金字塔的构建分为两部分：1、对图像做不同尺度的高斯模糊；2、对图像做降采样（隔点采样）；如下图所示，原图像作为金字塔的第一层，每次将采样所得到的新图像为金字塔的一层（每层一张图像），每个金字塔共n层。金字塔的层数根据图像的原始大小和塔顶图像的大小共同决定。    \n",
    "![高斯金字塔](http://px71ub40t.bkt.clouddn.com/%E9%AB%98%E6%96%AF%E9%87%91%E5%AD%97%E5%A1%941.png)   \n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;为了让尺度体现其连续性，高斯金字塔在简单降采样的基础上加上了高斯滤波，将图像金字塔每层的一张图像使用不同参数做高斯模糊，使得金字塔的每层含有多张高斯模糊图像，将金字塔每层多张图像合称为一组(Octave)，金字塔每层只有一组图像，组数和金字塔层数相等，使每组含有多张(也叫层Interval)图像。另外，降采样时，高斯金字塔上一组图像的初始图像(底层图像)是由前一组图像的倒数第三张图像隔点采样得到的。如下图：  \n",
    "![高斯金字塔](http://px71ub40t.bkt.clouddn.com/%E9%AB%98%E6%96%AF%E9%87%91%E5%AD%97%E5%A1%942.png)   \n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;在实际计算时，使用高斯金字塔每组中相邻的上下两层图像相减，得到高斯差分图像。这样就能得到候选的sift特征点。\n",
    "![高斯金字塔](http://px71ub40t.bkt.clouddn.com/%E9%AB%98%E6%96%AF%E9%87%91%E5%AD%97%E5%A1%943.png)    \n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;为了使描述符具有旋转不变性，需要利用图像的局部特征为给每一个关键点分配一个基准方向。使用图像梯度的方法求取局部结构的稳定方向。对于在DOG金字塔中检测出的关键点点，采集其所在高斯金字塔图像3σ邻域窗口内像素的梯度和方向分布特征。梯度的模值和方向如下：\n",
    "![方向](http://px71ub40t.bkt.clouddn.com/%E6%96%B9%E5%90%91%E5%9B%BE1.png)   \n",
    "L为关键点所在的尺度空间值，按Lowe的建议，梯度的模值m(x,y)按σ=1.5σ_oct的高斯分布加成，按尺度采样的3σ原则，邻域窗口半径为3x1.5σ_oct。  \n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;在完成关键点的梯度计算后，使用直方图统计邻域内像素的梯度和方向。梯度直方图将0~360度的方向范围分为36个柱(bins)，其中每柱10度。如下图所示，直方图的峰值方向代表了关键点的主方向，(为简化，图中只画了八个方向的直方图)。  \n",
    "![方向](http://px71ub40t.bkt.clouddn.com/%E6%96%B9%E5%90%91%E5%9B%BE2.png)   \n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;方向直方图的峰值则代表了该特征点处邻域梯度的方向，以直方图中最大值作为该关键点的主方向。为了增强匹配的鲁棒性，只保留峰值大于主方向峰值80％的方向作为该关键点的辅方向。因此，对于同一梯度值的多个峰值的关键点位置，在相同位置和尺度将会有多个关键点被创建但方向不同。仅有15％的关键点被赋予多个方向，但可以明显的提高关键点匹配的稳定性。\n",
    "\n",
    "**ORB算子原理：**  ORB是一种快速特征点提取和描述的算法。ORB算法分为两部分，分别是特征点提取和特征点描述。特征提取是由FAST（Features from  Accelerated Segment Test）算法发展来的，特征点描述是根据BRIEF（Binary Robust IndependentElementary Features）特征描述算法改进的。ORB特征是将FAST特征点的检测方法与BRIEF特征描述子结合起来，并在它们原来的基础上做了改进与优化。  \n",
    "\n",
    "\n",
    "oFast特征提取：  \n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;步骤一：粗提取。判断特征点：从图像中选取一点P，以P为圆心画一个半径为3像素的圆。圆周上如果有连续N个像素点的灰度值比P点的灰度值大或小，则认为P为特征点。这就是大家经常说的FAST-N。有FAST-9、FAST-10、FAST-11、FAST-12，大家使用比较多的是FAST-9和FAST-12。  \n",
    "快速算法：为了加快特征点的提取，快速排出非特征点，首先检测1、5、9、13位置上的灰度值，如果P是特征点，那么这四个位置上有3个或3个以上的的像素值都大于或者小于P点的灰度值。如果不满足，则直接排出此点。  \n",
    "![oFast](http://px71ub40t.bkt.clouddn.com/oFast.png)    \n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;步骤二：筛选最优特征点。机器学习的方法筛选最优特征点。简单来说就是使用ID3算法训练一个决策树，将特征点圆周上的16个像素输入决策树中，以此来筛选出最优的FAST特征点。具体步骤如下：  \n",
    "1.选取进行角点提取的应用场景下的一组训练图像。  \n",
    "2.使用FAST角点检测算法找出训练图像上的所有角点。  \n",
    "3.对于每一个角点，将其周围的16个像素存储成一个向量。对所有图像都这样做构建一个特征向量。  \n",
    "4.每一个角点的16像素点都属于下列三类中的一种，像素点因此被分成三个子集：Pd, Ps, Pb。  \n",
    "![oFast](http://px71ub40t.bkt.clouddn.com/oFast1.png)    \n",
    "5.定义一个新的布尔变量Kp ，如果是角点就设置为True，否则就设置为False。  \n",
    "6.使用ID3算法来查询每一个子集。  \n",
    "7.递归计算所有的子集直到它的熵为0。  \n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;步骤三：使用非极大值抑制算法去除临近位置多个特征点。  \n",
    "1.计算特征点出的FAST得分值s（像素点与周围16个像素点差值的绝对值之和）。  \n",
    "2.以特征点p为中心的一个邻域（如3x3或5x5）内，若有多个特征点，则判断每个特征点的s值。  \n",
    "3.若p是邻域所有特征点中响应值最大的，则保留；否则，抑制。若邻域内只有一个特征点，则保留。得分计算公式如下（公式中用V表示得分，t表示阈值）：\n",
    "![oFast](http://px71ub40t.bkt.clouddn.com/oFast2.png)    \n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;步骤四：建立金字塔以实现特征点多尺度不变性。   \n",
    "1.设置一个比例因子scaleFactor（opencv默认为1.2）和金字塔的层数nlevels（Opencv默认为8）。   \n",
    "2.将原图像按比例因子缩小成nlevels幅图像。  \n",
    "3.缩放后的图像为：I'= I/scaleFactor^k(k=1,2,…, nlevels)。nlevels幅不同比例的图像提取特征点总和作为这幅图像的oFAST特征点。  \n",
    "![oFast](http://px71ub40t.bkt.clouddn.com/oFast3.png)    \n",
    "4.特征点的旋转不变性。ORB算法提出使用矩（moment）法来确定FAST特征点的方向。也就是说通过矩来计算特征点以r为半径范围内的质心，特征点坐标到质心形成一个向量作为该特征点的方向。矩定义如下：  \n",
    "![oFast](http://px71ub40t.bkt.clouddn.com/oFast4.png)    \n",
    "其中，I(x,y)为图像灰度表达式。该矩的质心为：   \n",
    "![oFast](http://px71ub40t.bkt.clouddn.com/oFast5.png)    \n",
    "假设角点坐标为O，则向量的角度即为该特征点的方向。计算公式如下：   \n",
    "![oFast](http://px71ub40t.bkt.clouddn.com/oFast6.png)    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "rBRIEF特征描述：是在BRIEF特征描述的基础上加入旋转因子改进的。下面先介绍BRIEF特征提取方法，BRIEF算法计算出来的是一个二进制串的特征描述符。它是在一个特征点的邻域内，选择n对像素点pi、qi（i=1,2,…,n）。比较每个点对的灰度值的大小，如果I(pi)>I(qi)，则生成二进制串中的1，否则为0。所有的点对都进行比较，则生成长度为n的二进制串。一般n取128、256或512。另外，值得注意的是为了增加特征描述符的抗噪性，算法首先需要对图像进行高斯平滑处理。在ORB算法中，在这个地方进行了改进，在使用高斯函数进行平滑后，又用了其他操作，使其更加的具有抗噪性。在旋转不是非常厉害的图像里，用BRIEF生成的描述子的匹配质量非常高，但在旋转大于30°后，BRIEF的匹配率快速降到0左右，因此我们需要对BRIEF进行改进。\n",
    "\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;为了改进BRIEF算法，首先建立300k个特征点测试集。对于测试集中的每个点，考虑其31x31邻域。在对图像进行高斯平滑之后，使用邻域中的某个点的5x5邻域灰度平均值来代替某个点的值，进而比较点对的大小。使用积分图像加快求取5x5邻域灰度平均值的速度。在31x31的邻域内共有(31-5+1)x(31-5+1)=729个这样的子窗口，那么取点对的方法共有M=265356种，我们就要在这Ｍ种方法中选取256种取法，使这256种取法之间的相关性最小。  \n",
    "选取方法如下：  \n",
    "1.在300k特征点的每个31x31邻域内按M种方法取点对，比较点对大小，形成一个300kxM的二进制矩阵Q。矩阵的每一列代表300k个点按某种取法得到的二进制数。  \n",
    "2.对Q矩阵的每一列求取平均值，按照平均值到0.5的距离重新对Q矩阵的列向量排序，形成矩阵T。  \n",
    "![image.png](http://px71ub40t.bkt.clouddn.com/rBriff.png)    \n",
    "3.将T的第一列向量放到R中。  \n",
    "4.取T的下一列向量和R中的所有列向量计算相关性，如果相关系数小于设定的阈值，则将T中的该列向量移至R中。  \n",
    "5.按照 4的方式不断进行操作，直到R中的向量数量为256。  \n",
    "通过这种方法就选取了这256种取点对的方法。这就是rBRIEF算法。  \n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
